import java.util.*;

class Solution {
    HashMap<Character, Set<Character>> hash = new HashMap<>();
    HashMap<Character, Integer> in = new HashMap<>();


    public String alienOrder(String[] words) {
        for (String word : words) {
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                in.put(c, 0);
            }
        }


        for (int i = 0; i < words.length; i++) {
            char[] word = words[i].toCharArray();
            for (int j = i + 1; j < words.length; j++) {
                char[] word1 = words[j].toCharArray();
                int k = 0;
                for (k = 0; k < word.length && k < word1.length; k++) {
                    if (word[k] != word1[k]) {
                        Set<Character> set = hash.computeIfAbsent(word[k], a -> new HashSet<Character>());
                        if (!set.contains(word1[k])) {
                            set.add(word1[k]);
                            in.put(word1[k], in.get(word1[k]) + 1);
                        }
                        break;
                    }

                }
                if (k == word1.length && k < word.length) return "";
            }
        }
        return bfs(hash, in);

    }

    public String bfs(HashMap<Character, Set<Character>> hash, HashMap<Character, Integer> in) {
        Queue<Character> q = new LinkedList<>();
        for (char c : in.keySet()) {
            if (in.get(c) == 0) {
                q.add(c);
            }
        }
        StringBuffer s = new StringBuffer();

        while (!q.isEmpty()) {
            char cur = q.poll();
            Set<Character> list = hash.get(cur);
            s.append(cur);
            if(list!=null)
                for (char c1 : list) {
                    in.put(c1, in.get(c1) - 1);
                    if (in.get(c1) == 0) q.add(c1);
                }

        }

        for(char c:in.keySet()){
            if(in.get(c)!=0) return "";
        }



        return s.toString();

    }
}


